package LearnAlgorithm.e_多维数组and矩阵;

/*
[1,-2,3,5,-2,6,-1],子数组这样定义的：
这是元素数=6的子数组：
	[1,-2,3,5,-2,6]
	[-2,3,5,-2,6,-1]
这是元素数=5的子数组：
	[1,-2,3,5,-2]
	[-2,3,5,-2,6]
	[3,5,-2,6,-1]
就是说子数组必须是连续的，别把子集与子数组搞混了！！！！


给定一个数组arr ,返回子数组的最大累加和
例:
arr=[1,-2,3,5,-2,6,-1];所有的子数组中[3,5,-2,6]可以累加出最大的和12
所以返回12
 */
public class e一维数组返回子数组最大累加和 {
	public static void main(String[] args) {
		int[] arr = new int[] {1,-2,3,5,-2,6,-1};
		System.out.println(find(arr));
	}
	
	/**
	 * O(N)
	 * 不用担心有情况没考虑到
	 * 这个算法考虑到了全部的子数组情况了！！！！！
	 * @param arr
	 * @return
	 */
	public static int find(int[] arr) {
		if (arr.length == 0) {//判断数组是否为空
			return 0;
		}
		int sumI = arr[0];//定义当前元素A从i开始的“当前累加值”；默认初始化成首值
		int maxSum = sumI;//定义“目标子数组的最大累加的数值”
		int leftIndex = 0;//定义“目标子数组的开始索引”
		int rightIndex = 0;//定义“目标子数组的结束索引”
		for (int i = 1; i < arr.length; i++) {//开始遍历；从A的下一个元素B开始
			if (sumI >= 0) {//判断“当前累加值”是否为正数
				sumI += arr[i];//正数，就继续累加
			} else {
				sumI = arr[i];//负数，代表从A的索引开始的“累加”一定不会成为最大累加；A更新为当前遍历的元素(索引是i)
				leftIndex = i;//更新开始索引
			}
			if (sumI > maxSum) {//判断当前累加值是否>之前遍历过程中更新的“目标子数组的最大累加的数值”
				maxSum = sumI;//通过，更新“目标子数组的最大累加的数值”
				rightIndex = i;//更新结束索引
			}
		}
		System.out.println(leftIndex + "," + rightIndex);
		return maxSum;//循环结束，返回“目标子数组的最大累加的数值”
	}
	
	/**
	 * O(N^2)
	 * @param arr
	 * @return
	 */
	public static int forceFind(int[] arr) {
		if (arr.length == 0) {//判断数组是否为空
			return 0;
		}
		int maxSum = arr[0];//默认数组首值作为“目标子数组的最大累加的数值”
		for (int i = 0; i < arr.length; i++) {//开始遍历数组
			int sum = arr[i];//定义当前i循环，从开始元素A，遍历到当前元素B，这所有元素的累加值
			int maxOfI = sum;//定义当前i循环的最大累加数值
			for (int j = i + 1; j < arr.length; j++) {//从开始元素A后第一个元素B开始累加
				sum += arr[j];//累加
				if (sum > maxOfI) {//判断累加值>当前i循环的最大累加数值
					maxOfI = sum;//更新当前i循环的最大累加数值
				}
			}
			if (maxOfI > maxSum) {//判断当前i循环的最大累加数值>之前遍历过程中更新的“目标子数组的最大累加的数值”
				maxSum = maxOfI;//更新“目标子数组的最大累加的数值”
			}
		}
		return maxSum;//循环结束，返回“目标子数组的最大累加的数值”
	}
	
	
}
